package top.minuy.structure.graph.route.euler;

import top.minuy.structure.graph.cc.bfs.CC;
import top.minuy.structure.graph.representations.table.Graph;

/**
 * 检测是否有欧拉回路
 *
 * @author Minuy
 * @time 20:22
 * @date 2021/11/24
 */
public class EulerDetection {

    boolean hasEulerLoop;

    public EulerDetection(Graph g) {

        if (g.isDirected()){
            throw new IllegalArgumentException("EulerDetection only works in undirected graph.");
        }

//        int cnt = 0;
//        {
//            boolean[] isVisited = new boolean[g.V()];
//
//            // 广度优先遍历
//            int v = 0;
//            ArrayList<Integer> queue = new ArrayList<>();
//            queue.add(v);
//            isVisited[v] = true;
//            cnt++;
//            while (!queue.isEmpty()) {
//                v = queue.remove(0);
//
//                for (int w : g.adj(v)) {
//                    if (!isVisited[w]) {
//                        queue.add(w);
//                        isVisited[w] = true;
//                        cnt++;
//                    }
//                }
//            }
//        }

        CC cc = new CC(g);

        // 不止一个联通分量
        if (cc.count() != 1) {
            hasEulerLoop = false;
            return;
        }

//        if (cnt != g.V()) {
//            hasEulerLoop = false;
//            return;
//        }


        for (int v = 0; v < g.V(); v++) {
            if (g.degree(v) % 2 != 0) {
                hasEulerLoop = false;
                return;
            }
        }

        hasEulerLoop = true;
    }

    public boolean hasEulerLoop() {
        return hasEulerLoop;
    }

    @Override
    public String toString() {
        return String.valueOf(hasEulerLoop());
    }
}
